package com.xigua.字符串;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 给出一个字符串数组 words 组成的一本英语词典。返回 words
 * 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。
 *
 *若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。
 *
 * @date 2022/3/1719:28
 */
public class _720_词典中最长的单词 {

    public static void main(String[] args) {
        String words[] = new String[]{"a", "banana", "app", "appl", "ap", "apply", "apple"};
        String longestWord = longestWord(words);
        System.out.println(longestWord);
    }

    public static String longestWord(String[] words) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        String longest = "";
        for (String word : words) {
            if (trie.search(word)){
                if (word.length() > longest.length() || (word.length() == longest.length() && word.compareTo(longest) < 0)){
                    longest = word;
                }
            }
        }
        return longest;
    }
}

class Trie {

    private boolean isEnd;
    private Trie[] child;

    public Trie() {
        isEnd = false;
        child = new Trie[26];
    }

    public void insert(String word) {
        Trie trie = this;
        int length = word.length();
        for (int i = 0; i < length; i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (trie.child[index] == null){
                trie.child[index] = new Trie();
            }
            trie = trie.child[index];
        }
        trie.isEnd = true;
    }

    public boolean search(String word) {
        return searchPrefix(word) != null &&  searchPrefix(word).isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie trie = this;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - 'a';
            if (trie.child[index] == null || !trie.child[index].isEnd) return null;
            trie = trie.child[index];
        }
        return  trie;
    }
}

